A content addressable memory (CAM) is a type of computer memory that allows for high speed searches of a specific data pattern within its memory cells, which are organized as an array having rows and columns. A different data pattern may be stored in each row of the CAM. Data to be checked can be supplied to an input of the CAM, and the CAM may then compare the input to each row of the CAM array. If the CAM determines that the input matches one or more rows, the CAM returns a signal indicating the row or rows that match. Typically, if more than one row matches the input data, the CAM returns a signal indicating only one of the matching rows based on some priority scheme. For example, the highest matching row in the CAM may be indicated.
A CAM may be used to determine whether a certain data pattern is in a stream of data, such as data read from a hard disk drive or data received via a network. This may be useful for example, for making forwarding decisions, virus detection, network intrusion detection, etc., e.g., at a network switch. For instance, the stream of data may be analyzed to determine if it includes any data patterns that match any of the entries in a list (dictionary) of known virus patterns stored in the CAM. Upon detection of a pattern match relating to a virus, desired actions could be taken such as further analysis, repair, quarantine, or deletion of the data containing the virus. As another example, a network security device may analyze an incoming packet to determine if it is from one of several IP source addresses stored in the CAM. Upon match of a source IP address in the CAM, desired actions could be taken such as forwarding the packet, dropping the packet, trapping the packet for further analysis, etc.
Several different functions or applications may utilize one CAM. In the context of network security, for example, an “IP source guard” application may utilize the CAM to identify packets having particular Internet Protocol (IP) source addresses, and a “Syn flood attack” application may utilize the CAM to identify packets with the “Syn” flag set in the Transmission Control Protocol (TCP) header. When several applications utilize a CAM, each application may have a plurality of patterns (or rules) that the application seeks to identify using the CAM. Generally, each rule corresponds to one row in the CAM. But when multiple applications utilize the CAM, the rules of the different applications may multiply each other (sometimes referred to as “Cartesian multiplication”). For example, if there are three applications, A, B, and C, each having a set of ten rules, the total number N of rules that need to be stored in the CAM may be N=10*10*10=1000 (i.e., 1000 rows of storage needed in the CAM). To avoid Cartesian multiplication, multiple CAM lookups may instead be utilized, but increasing the number of lookups may decrease throughput and/or increase costs.